1. Field of the Invention
The present invention relates to a method of translating a source operation to a target operation. For example, the method may be used to permit efficient computation with integer values whose bit-width is not a multiple of a native integer bit-width of a target machine, such as a computer. Another application of such a method to in the simulation of high-level hardware description languages. The invention also relates to a computer program for performing such a method, a storage medium containing such a program, a computer programmed by such a program and a translation produced by such a method.
2. Description of the Related Art
Hardware description languages such as VHDL (IEEE Computer Society. IEEE Standard VHDL Lanquage Refrence Manual. New York, USA. June 1994. IEEE Std 1076 1993 and Verilog HDL (IEEE Computer Society. IEEE Standard Hardware Description Language Based on the Verilog Hardware Description Language. New York, USA. 1996. IEEE Std 1364 1995.) can be used to describe the behaviour of hardware circuits. These languages support the description of circuits involving integer arithmetic by supplying appropriate numeric types and operators. In order to design hardware efficiently, the numeric types are usually parameterised by the bit-widths of the integer values of the type.
For instance, the IEEE 1076.3 NUMERIC_STD VHDL library (IEEE Computer Society. IEEE Standard Hardware Description Language Based on the Verilog Hardware Description language, New York, USA, 1996. IEEE Std 1364 1995) defines the UNSIGNED and SIGNED integer types based on the type of bit vectors STD_LOGIC VECTOR. Bit vectors are fixed-length lists of bit values which include the values 0 and 1 as well as other states such as U (uninitialised) and Z (high impedance). Although the length of the bit vectors (and therefore of the numeric types) is fixed, one can use several types of bit vectors (each having different lengths) in a hardware design. Note that since the individual bits of a VHDL numeric type can have values other than 0 and 1, a numeric type contains several values that do not correspond to valid integers.
High-level hardware description languages, such as the Bach language (Akihisa Yamada, Koichi Nishida, Ryoji Sakurai, Andrew Kay, Toshio Nomura and Takashi Kambe. Hardware synthesis with the BACH system. International Symposium on Circuits and Systems, 1999, GB2 317 245), can be used to describe hardware at a level of abstraction usually used in programming languages such as C (Brian W. Kernihan and Dennis M. Ritchie. The C Programming Language, Prentice-Hall, USA, second edition, 1988).
Since the C language, and programming languages in general, are designed to be used to program some particular architecture, the semantics of their integer types and expressions usually depend on the target architecture being programmed. For example, the C language (Brian W. Kernihan and Dennis M. Ritchie. The C Programming Language, Prentice-Hall, USA, second edition, 1988) supplies the int and unsigned int types which correspond to signed and unsigned integers whose bit-width is naturally supported by the target machine. The C integer types are too inflexible to be used for the efficient design of hardware and therefore the Bach hardware description language extends C by exact width integer types, such as intw and unsigned into for signed and unsigned v-bit integers, respectively.
One of the many advantages of using a high-level, programming-language based, hardware description language like Bach over using a lower level one such as VHDL is the ability to simulate (on a general purpose architecture) the behaviour of designs at much higher speeds. For example, because of the particular level of abstraction of the VHDL numeric types described earlier, one cannot use the integer arithmetic of the target machine used for simulation directly. In general, one would have to represent every bit value of a numeric type as a separate byte/word on the target machine and therefore the simulation of VHDL arithmetic operations can be much slower than the native arithmetic of the target machine. Although Bach arithmetic is more similar to the native arithmetic of a target machine than VHDL numeric arithmetic is, one still cannot use the native target machine arithmetic naively because of the difference in the bit-widths. One therefore needs to develop methods for the correct and efficient simulation of the exact width of the arithmetic usually used in hardware descriptions.
Retargetable compilers, such as the Valen-C compiler (Graduate School of Information Science and Electrical Engineering (Kyushu University), Advanced Software Technology and Mechatronics Research Institute of Kyoto, Institute of Systems and Information Technologies (Kyushu) and Mitsubishi Electric Corporation. Valen-C Compiler Development Ddocument (English Version 1.01). Information Technology promotion Agency, Japan, April 1998), can be used to compile an input source program to the assembly/machine language of different target machines. The input language of the Valen-C compiler is the Valen-C programming language which also extends the ANSI C language by exact width integer types. The programmer can specify integer types of the form intw where w is any non-zero natural number representing the width of the type. However, the semantics of the Valen-C integer arithmetic is still dependent on the target architecture and an integer type intw is actually defined as being at least w bits long and Its width is a multiple of the word size of the target machine. As a result, the behaviour of the compiled code differs from one target machine to another.
De Coster et al, xe2x80x9cCode generation for compiled bit-time simulation of DSP applicationsxe2x80x9d, 11th International Symposium on System Synthesis (ISSS""98) 2-4 Dec. 1998, Hsinch, Taiwan (IEEE Computer Society Publications) pp 9-14 disclose a method intended for translating, fixed point integer arithmetic into standard integer arithmetic for the efficient simulation of digital signal processing (DSP) applications. However, no attempt is made to minimise value correcting operations in the resulting integer arithmetic expressions, which thus make inefficient use of target machine resources.
EP 0 626 640 and EP 0 626 641 disclose techniques for converting high level processing languages into machine language. These techniques require the intervention of a user to assess whether the value of an operation is likely to overflow when a program is executed by a computer. If so, a value correction operation is performed and may comprise a masking operation or a sign-extending operation depending on whether the operation is unsigned or signed.
According to a first aspect of the invention, there is provided a method of translating a source operation on at least one source operand comprising a binary integer of a first bit-width to a corresponding target operation for evaluation by a processor which performs integer operations on binary integers of a second bit-width which is greater than the first bit-width, the method comprising: translating the source operation to a target operation having at least one target operand; identifying whether the value of unused bits of the or each target operand affects the value of the target operation and whether the target operand or any of the target operands is capable of having one or more unused bits of inappropriate value; and, if so, adding to the target operation a correcting operation for correcting the value of each of the one or more bits of inappropriate value before performing the target operation.
The at least one source operand may comprise at least one constant.
The at least one source operand may comprise at least one variable.
The at least one source operand may comprise at least one sub-operation.
The source operation may comprise an arithmetic operation. The identifying step may comprise identifying an unsigned unmasked target operand and the correcting step may comprise a masking step. The first bit-width may be w bits and the masking step may comprise performing a bit-wise AND operation between the unsigned unmasked target operand and a binary representation of (2w-1). The identifying step may comprise identifying a signed non-sign-extended target operand and the correcting step may comprise a sign-extending step.
The source operation may comprise a relational operation and the correcting step may comprise a monotonic operation.
According to a second aspect of the invention, there is provided a computer program for performing a method according to the first aspect of the invention.
According to as third aspect of the invention, there is provided a storage medium containing a computer program according to the second aspect of the invention.
According to a fourth aspect of the invention, there is provided a computer programmed by a program according to the second aspect of the invention.
According to a fifth aspect of the invention, there is provided a translation produced by a method according to a first aspect of the invention.
The term xe2x80x9cunused bitxe2x80x9d of a target operand refers to any bit thereof which is not used to represent the value of a corresponding source operand.
The term xe2x80x9cinappropriate valuexe2x80x9d of an unused bit refers to a value of an unused bit which, if present in the target operand, will result in the target operation being evaluated to a value different from that of the corresponding source operation.
It is thus possible to provide a method for the efficient computation of arithmetic and relational expressions involving integers of any bit-widths using a given device which is only capable of computing integer arithmetic expressions of certain bit-widths.
For a given device or mechanism, called the target machine, which is capable of computing integer arithmetic of some specified widths, say, W1, w2 etc., such a method translates arithmetic expressions involving integers of any width into efficient arithmetic expressions involving integers of the specified widths. The language of expressions involving integer arithmetic of any width is referred to as the source language. Similarly, the language of expressions involving integers of the given widths w1, w2, etc., is referred to as the target language. Using this method:
An integer atomic expression (such as a constant or variable) having width w is represented by an atomic expression whose width is that of the narrowest target language integer that is at least w bits wide. For example, an unsigned atomic expression of width 5 is represented by an atomic expression of width 16 if the target language contains integers of width 16, 32, 48, etc.
20(US)xe2x86x9220(U16) 
The notation x(Uw) denotes the fact that the expression has an unsigned integer type of width w and xxe2x86x92y denotes the fact that the source expression x is translated into the target expression y.
Arithmetic operations in the target language are used whenever possible.
For example:
a(US)+b(US)xe2x86x92a(U16)+b(U16) 
Because of the different widths in the source language and target language, the values of the target operations may differ from those in the source language:
20(US)+30(US)=18(US) while 20(U16)+30(16) =50(16) 
and therefore value correcting operations may be required in order to ensure that the value of operations in the target expression is the same as those in the source expression when this in required:
a(US)+b(US)xe2x86x92(a(U16) +b(U16))and31(U16) 
where and is the bitwise AND operator. The operation X(U16) and 31(U16) corrects the 16 bit value stored in the expression X(U16) assuming that it represents a 5 bit unsigned value.
Value correcting operations are not applied to every sub-expression that is translated, but only when such operations are required. For example, the expression:
(a(US)+b(US))*c(US))/(d(US)+e(US)) 
is not naively translated into:
((((a16)+b(U16))and31(U16))*c(U16))and31(U16))/ 
((d(U16)+e(U16))and31(U16)and 31(U16)) 
which uses 8 target machine operations, but into the more efficient:
(((a(U16)+b(U16))*c(U16))and31(U16))/((d(U16)+e(U16))and31(U16)) 
which uses 6 operations.
This is achieved by using an internal representation of the target expressions (stored in memory locations, or registers, on the machine used to translate source expression representations into target machine representations) which includes
1. the representation of the target machine expression;
2. together with the following additional information: the sign of the expression, the width of the original expression (called the significant width), the width of the target expression (called the representative width), and some information on the possible values of the bits in the integer value of the target expressions that are not used to store the value of the source expression (called the high-bit properties). The bits in the target expression values that are not used to store the value of the source expression are called the unused bits.
This information is called the additional type information. Of particular importance is the high-bit properties information which states whether the following two properties are satisfied:
the masked property which states that all the unused bits are 0.
the sign-extended property which states that all the unused bits are the same as the most-significant bit of the value of the source expression.
These two properties are significant because,
if the expression is unsigned, then the value of the source expression is the same as the value of the target expression if and only if the target expression has the masked property.
if the expression is signed, then the value of the source expression is the same as the value of the target expression if and only if the target expression has the sign-extended property.
By using additional memory locations to store the additional type information (apart from the memory locations required to store the representation of the target machine expression), such a translation method can insert the appropriate value correcting operations in target expression only when:
1. the value of the target expression is different from that of the source expression (that is, when the expression is unsigned and does not have the masked property, or when it is signed and does not have the sign-extended property), and
2. the operation being translated requires the correct target expression values of its operands. Certain operations, such as + and * do not require the correct value for their target operands as long as the values in the significant bits are the same as the values in the bits of the source expression. As a result their operands do not need to be value-corrected when the target expression is constructed.
Other operations, such as ¥ require correct values for their operands, and therefore they have to be value corrected if their appropriate high-bit property (masked if the expression is unsigned, sign-extended otherwise) is not set. The result of certain operations (such as ¥, but not + or *) is correct and therefore the appropriate high-bit property can be set in the additional type information of the target expression so that no value correction on the resulting expression is required later.
Since value-correcting operations are not inserted naively in all operations, the resulting target expression is more efficient.
Such a method can be used when arithmetic involving integers of any bit-widths needs to be computed on a processor or any device which can efficiently compute arithmetic operations of certain bit-widths only. Industrial applications of such a method include:
The efficient simulation of high-level descriptions (using Bach, or otherwise) of arithmetic circuits on some specified target machine. Hardware is described in the Bach high-level language, and a low-level synthesizable industrial-strength hardware description is generated automatically. Since the hardware designer uses a high-level language instead of a lower level one (such as VHDL), the design process is much quicker, and therefore cheaper, than traditional hardware design processes. The present method may be used in the simulation phase of the Bach design flow, where the Bach hardware description is validated before the actual hardware is synthesised. This makes the simulation phase much faster than the use of naive methods, therefore reducing the time spent in hardware design.
The efficient simulation or compilation of arithmetic operations targeted to a machine whose native integer arithmetic is different from the one used for simulation. For example, a program targetted to a particular processor (which may be slow or not readily available during the implementation stage) can be simulated on a faster, readily available processor whose architecture is different from the target machine architecture.
The efficient simulation of the designs of embedded systems where the efficient simulation of both hardware and software is required.
Advantages which are readily achievable include:
The target expressions generated by such a method are efficient since the native integer arithmetic of the target machine is used directly and the number of value correcting operations is reduced.
The translation method itself is not time/space expensive and can therefore be used in applications where a quick compilation of the source expressions into the target expressions is required.